package com.zjj.algorithm.learning.leetcode.matrix;

import java.util.Arrays;

/**
 * 498. 对角线遍历 中档题
 * 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
 * <p>
 * 输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[1,2,4,7,5,3,6,8,9]
 * 示例 2：
 * <p>
 * 输入：mat = [[1,2],[3,4]]
 * 输出：[1,2,3,4]
 *
 * @author zjj_admin
 * @date 2022/11/28 15:12
 */
public class DiagonalTraverse {

    public static void main(String[] args) {
        int[][] mat1 = {
                {1, 2},
                {4, 5},
                {7, 8}
        };

        int[][] mat2 = {
                {1}
        };
        int[] res = findDiagonalOrder(mat1);
        System.out.println("res = " + Arrays.toString(res));

    }

    /**
     * 时间
     * 2 ms
     * 击败
     * 63.95%
     * 内存
     * 43.3 MB
     * 击败
     * 50.84%
     *
     * @param mat
     * @return
     */
    public static int[] findDiagonalOrder(int[][] mat) {
        int h = mat.length;
        int w = mat[0].length;
        int[] res = new int[h * w];
        int x = 0, y = 0, i = 0;
        //表示此时是在向上走还是向下走
        boolean up = true;
        res[i] = mat[y][x];
        while (true) {
            if (x == w - 1 && y == h - 1) {
                break;
            }
            //当是在向右上方遍历时
            if (up) {
                x = x + 1;
                y = y - 1;
                //当横坐标超出了矩阵的宽度时
                if (x >= w) {
                    //让x位于最后一列
                    x = w - 1;
                    //让 y 向下移动两位
                    y = y + 2;
                    //此时需要向左下方遍历了
                    up = false;
                }
                if (y <= -1) {
                    y = y + 1;
                    up = false;
                }
            } else {
                //当是在向最下方遍历时
                x = x - 1;
                y = y + 1;
                //当纵坐标超出矩阵的高度时
                if (y >= h) {
                    //让纵坐标指向最后一列
                    y = h - 1;
                    //横坐标向右移动两位
                    x = x + 2;
                    up = true;
                }
                //当横坐标越出矩阵左侧时
                if (x <= -1) {
                    //让纵坐标位于第一列
                    x = x + 1;
                    up = true;
                }
            }
            i++;
            res[i] = mat[y][x];
        }
        return res;
    }


}
